package cn.djb.day19;

/**
 * 给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
 * <p>
 * 百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
 */
class Solution_3 {

    TreeNode p, q;
    boolean isExit;


    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        this.p = p;
        this.q = q;
        return  dfs(root);
    }

    private TreeNode dfs(TreeNode node) {
        if (node == null) {
            return null;
        }
        if (node == this.p || node == this.q) {
            return node;
        }

        TreeNode left = dfs(node.left);

        TreeNode right = dfs(node.right);

        if (left!=null && right != null){
            return node;
        }
        if (left != null){
            return left;
        }
        if (right != null){
            return right;
        }
        return null;
    }


    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }
}